/**
 * 
 * @param val 
 * @param val1 
 * @returns 
 */
function compareFn(val:number,val1:number):number{
    return val - val1;
}
function swap(arr:any[],i:number,j:number):void{
    [arr[j],arr[i]] = [arr[i],arr[j]]
}
export function BubbleSort<T>(arr:T[],fn:(val:T,val1:T)=>number = compareFn as any){
    for(let i = 0;i<arr.length-1;i++){
        for(let j = i+1;j<arr.length;j++){
            if(fn(arr[i],arr[j]) > 0){
                swap(arr,i,j);
            }
        }
    }
    return arr;
}
/**
 * 选择排序
 * 在数组种选择最小的排到嘴前面
 * @param arr 
 * @param fn 
 * @returns 
 */
export function selectionSort<T>(arr:T[],fn:(val:T,val1:T)=>number = compareFn as any){
    for(let i = 0;i<arr.length;i++){
        let minIndex = i
        for(let j = i+1;j<arr.length;j++){
            if(Number(fn(arr[minIndex],arr[j])) > 0){
                minIndex = j;
            }
        }
        if(i !== minIndex){
            swap(arr,i,minIndex);
        }
    }
    return arr;
}
/**
 * 插入排序
 * 记录一个当前temp，后序值直接插入，最后再将temp插入
 * @param arr 
 * @param fn 
 */
export function insertionSort<T>(arr:T[],fn:(val:T,val1:T)=>number = compareFn as any){
    for(let i = 0;i<arr.length;i++){
        let j = i;
        let temp = arr[j];
        while(j>0 && fn(arr[j-1],arr[j]) > 0){
            arr[j] = arr[j-1];
            j--;
        }
        arr[j] = temp;
    }
    return arr;
}

function merge<T>(left:T[],right:T[],fn:(val:T,val1:T)=>number = compareFn as any):T[]{
    let j = 0,i = 0;
    let result = [];
    while(i<left.length && j < right.length){
        result.push(fn(left[i],right[j]) > 0 ? right[j++] : left[i++])
    }
    return result.concat(i < left.length ? left.slice(i) : right.slice(j));
}
/**
 * 归并排序
 * @param arr 
 * @param fn 
 * @returns 
 */
export function mergeSort<T>(arr:T[],fn:(val:T,val1:T)=>number = compareFn as any):T[]{
    if(arr.length === 1){
        return arr;
    }
    let middle = Math.floor(arr.length/2);
    let left = mergeSort(arr.slice(0,middle),fn)
    let right = mergeSort(arr.slice(middle,arr.length),fn)
    return merge(left,right,fn);
}
/**
 * 快速排序
 * @param arr 
 * @param fn 
 * @returns 
 */
export function quickSort<T>(arr:T[],fn:(val:T,val1:T)=>number = compareFn as any):T[]{
    function partition(arr:any[],left:number,right:number,fn:any){
        let pivot = arr[Math.floor((left+right)/2)];
        while(left <= right){
            while(fn(arr[left],pivot) < 0){
                left++;
            }
            while(fn(arr[right],pivot) > 0){
                right--;
            }
            if(left <= right){
                swap(arr,left,right);
                left++;
                right--;
            }
        }
        return left;
    }
    function quick(arr:any[],left:number,right:number,fn:any){
        if(arr.length <= 1){
            return arr;
        }
        let index = partition(arr,left,right,fn);
        if(left < index-1){
            quick(arr,left,index-1,fn);
        }
        if(index < right){
            quick(arr,index,right,fn);
        }
        return arr;
    }
    return quick(arr,0,arr.length-1,fn);
}
/**
 * 计数排序
 */
/**
 * 桶排序
 */
/**
 * 基数排序
 */